/**
 *	6.大质数是不是和小质数一样多，换句话说，在50000和51000之间的质数是不是和1000000到1001000之间的质数一样多？
 *	使用前面的程序计算0到1000之间有多少个质数，1000到2000之间有多少个质数？以此每隔1000类推，到1000000有多少个质数，
 *	每隔1000个数中质数的质量的数量呈什么趋势？
**/

#include <stdio.h>

#define MAX 	1000001

int Eratosthenes(char [], int max);

int main()
{
	int i;
	int sum = 0;
	int count = 0;
	char prime[MAX];
	int max;

	for(i = 1; i < MAX; i++)
		prime[i] = 1;

	for(max = 1000; max < MAX; max += 1000)
	{
		//count = Eratosthenes(prime, max) - sum;
		//printf("%d\t%d\t\n", max, count);
		//sum += count;
		count = Eratosthenes(prime, max);
		printf("%f\n",(float)max/count * 1000);
	}
}

int Eratosthenes(char prime[], int max)
{
	int count = 0;
	int i = 0;
	int i_p;
	int j;
	int j_p;

	for(i = 1; i < max; i++)
	{
		if(prime[i] == 1)
		{
			i_p = 2 * i + 1;
			for(j = 2 * i_p; j < max; j += i_p)
				if(j % 2 == 1 && prime[(j-1)/2] == 1)
				{
					j_p = (j - 1) / 2;
					prime[j_p] = 0;
					count++;
				}
		}
	}
	return count;
}
